package com.yu1996.stack;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PolandNotation {
    public static void main(String[] args) {
        /*
        //定义一个逆波兰表达式
        String nbl = "4 5 * 8 - 60 + 8 2 / +";
        //调用自己写的方法将逆波兰表达式转化成集合
        List<String> strings = PolandNotation.changeArray(nbl);
        //测试转化是否成功
//        System.out.println(strings);
        int res = PolandNotation.culculate(strings);
        System.out.println("计算结果是：" + res);
        */

        //测试将中缀表达式转化成成后缀表达式
        String experision = "1+((2+3)*4)-5";
//      测试将中缀表达式转换成集合
        List<String> conversion = PolandNotation.conversion(experision);
//        System.out.println(conversion);
        //测试将中缀表达式转换成后缀表达式
        List<String> strings = PolandNotation.suffixExpression(conversion);
        System.out.println(strings);
    }


    /**
     * @Description 将中缀表达式转换成后缀表达式
     * @Author xing
     * @Date 2019/8/11 15:28
     * @Param
     * @Return
     * @Exception
     */
    public static List<String> suffixExpression(List<String> ls) {
        //先定义符号栈
        Stack<String> stack = new Stack<>();
        //定义集合存放数字和符号
        List<String> array = new ArrayList<>();
        //遍历集合
        for (String str : ls) {
            //先判断几种特殊情况
            if (str.matches("\\d+")) {
                //如果是数字直接入集合
                array.add(str);
            } else if (str.equals("(")) {
                //如果是左括号  直接入栈
                stack.push(str);
            } else if (str.equals(")")) {
                //如果是  右括号  将栈中在（之前的所有符号入集合
                while (!stack.peek().equals("(")) {
                    array.add(stack.pop());
                }
                //再将（出栈
                stack.pop();
            } else {  //剩下加减乘除符号   编写判断优先级的类
                while (!stack.isEmpty() && Priority.comparePriority(stack.peek()) >= Priority.comparePriority(str)) {
                    array.add(stack.pop());
                }
                stack.push(str);
//                //如果当前字符比栈顶元素的优先级高  或者栈为空   直接入栈
//                if (stack.isEmpty() || Priority.comparePriority(str) > Priority.comparePriority(stack.peek())) {
//                    //直接将符号入栈
////                    array.add(str);
//                    stack.push(str);
//                } else {  //遍历栈中元素  将所有运算符优先级小的都入集合
//                    while (!stack.isEmpty() && Priority.comparePriority(str) >= Priority.comparePriority(stack.peek())) {
//                        array.add(stack.pop());
//                    }
//                    //再将运算符入栈
//                    stack.push(str);
//                }
            }

        }
        //最后再将栈中所有运算符依次入集合
        while (stack.size() != 0) {
            array.add(stack.pop());
        }

        //将集合输出
        return array;
    }

    /**
     * @Description 将中缀表达式转换成集合
     * @Author xing
     * @Date 2019/8/11 14:54
     * @Param
     * @Return
     * @Exception
     */
    public static List<String> conversion(String ls) {
        List<String> s = new ArrayList<>();
        //定义指针  遍历字符串
        int i = 0;
        //定义字符串  拼接多位数
        String str;
//        定义字符用于接收遍历的每个字符
        char c;
        do {
//            将遍历的字符取出
            //判断是否是非数字
            if ((c = ls.charAt(i)) < 48 || (c = ls.charAt(i)) > 57) {
                //直接将字符转成串 加入集合
                s.add(c + "");
                i++;
            } else {   //如果是数字  则需要判断是否是多位数
                //先拼串
                str = "";
                while (i < ls.length() && (c = ls.charAt(i)) >= 48 && (c = ls.charAt(i)) <= 57) {
                    str += c;
                    i++;
                }
                s.add(str);
            }
        } while (i < ls.length());
        return s;
    }

    /**
     * @Description 将逆波兰表达式转化成集合
     * @Author xing
     * @Date 2019/8/9 12:21
     * @Param
     * @Return
     * @Exception
     */
    public static List<String> changeArray(String lb) {
        //先将字符串转化成字符数组
        String[] s = lb.split(" ");
        //将转化的字符数组依次存入集合中
        List<String> strings = new ArrayList<String>();
        for (String str : s) {
            strings.add(str);
        }
        return strings;
    }

    public static int culculate(List<String> list) {
        //定义一个栈 用于存放数字
        Stack<String> stack = new Stack<>();
        //遍历集合  按照逆波兰的算法返回
        for (String str : list) {
            //判断是数字还是运算符
            if (str.matches("\\d+")) {
                //如果是数字  直接入栈
                stack.push(str);
            } else {
                //如果是运算符  取出数栈中的两个数将其运算结果返回栈中即可
                int num1 = Integer.parseInt(stack.pop());
                int num2 = Integer.parseInt(stack.pop());
                int res = 0;
                if (str.equals("+")) {
                    res = num1 + num2;
                } else if (str.equals("-")) {
                    res = num2 - num1;
                } else if (str.equals("*")) {
                    res = num2 * num1;
                } else if (str.equals("/")) {
                    res = num2 / num1;
                } else {
                    throw new RuntimeException("运算符不匹配");
                }
                //将运算结果入栈
                stack.push("" + res);
            }
        }
        //遍历结束后将集合中元素返回即可
        return Integer.parseInt(stack.pop());
    }
}


/**
 * @Description: 判断符号优先级的类
 * @author: xing
 * @Date: 2019/8/11 15:41
 */
class Priority {

    private static int ADD = 1;
    private static int SUB = 1;
    private static int MUL = 2;
    private static int DIV = 2;


    /**
     * @Description 判断符号优先级的方法
     * @Author xing
     * @Date 2019/8/11 15:42
     * @Param
     * @Return
     * @Exception
     */
    public static int comparePriority(String s) {
        int res = 0;
        switch (s) {
            case "+":
                res = ADD;
                break;
            case "-":
                res = SUB;
                break;
            case "*":
                res = MUL;
                break;
            case "/":
                res = DIV;
                break;
            case "(":
                break;
            default:
                System.out.println("输入符号不合法");
                break;
        }
        return res;
    }
}
